package javax;

public class Xp_0110 {
    //荷兰国旗问题、随机快速排序
    public static int[] sort(int[] arr,int L ,int R){
        if (L==R || arr.length<2){
            return arr;
        }
        int less = L-1;
        int more = R;
        while (L<R){
            if (arr[L]<arr[R]){
                XpUtils.swap(arr,++less ,L++);
            }else if (arr[L]>arr[R]){
                XpUtils.swap(arr,--more,L);
            }else {
                L++;
            }
        }
        int[] swap = XpUtils.swap(arr, more + 1, R);
        return swap;
    }
    public static int[] quickSort(int[] arr,int L,int R){
        if (L==R || arr.length<2){
            return arr;
        }
        if (L<R){
            XpUtils.swap(arr,L+(int)(Math.random()*(R-L+1)),R);
            int[] sort = sort(arr, L, R);
            quickSort(arr,L,sort[0] -1);
            quickSort(arr,sort[1]+1,L);
            return arr;
        }

        return arr;
    }
    public static void main(String[] args){
        int[] arr = {1,4,5,3,2,6};
        int[] ints = quickSort(arr, 0, arr.length - 1);
        XpUtils.print(ints);
    }
    /**
     * 1234567  ->7   O(n2)
     * 最好是平均位置  O(N.logn)
     * L-R中选择   所以快排存在长期期望（比较好 所以常用、常数低）   存在概率问题
     * 空间复杂度 分两块  但是要记p  所以空间复杂度O(logn)~O(n)
     */
}
